Graph Representations

Graph

A graph G consists of a set of the nonnegative number of vertices and a set of the nonnegative number of edges that connect two distinct vertices. It provides the ultimate flexibility to represent structure of data.

In this article, I will show two ways to how to represent a graph on a computer.

Graph ADT

In [6]:
trait GraphADT {
  def numVertices(): Int

  def numEdges(): Int

  // return the first neighbor of v
  def first(v: Int): Option[Int]

  // return the next neighbor of v after w
  def next(v: Int, w: Int): Option[Int]

  def setEdge(s: Int, g: Int, w: Int): Unit

  def delEdge(s: Int, g: Int): Unit

  def isEdge(s: Int, g: Int): Boolean

  def weight(s: Int, g: Int): Option[Int]

  def setMark(v: Int, value: Int): Unit

  def getMark(v: Int): Int
}
Out[6]:
defined trait GraphADT

Adjacency matrix

We can store all of the information of a graph by matrix, which is two-dimensional array. If there are $V$ vertices and $E$ edges, then the size of the matrix is $V^2$ and $E$ points are filled with the weight or distance of two corresponding vertices. It needs $\Theta(V^2)$ space, and since the maximum number of edges is $V^2 - V$, it becomes space efficient when there are many edges compared to the vertices.

In [7]:
class MatrixGraph(n: Int) extends GraphADT {
  private val matrix: Array[Array[Int]] = Array.ofDim(n, n)
  private val mark: Array[Int] = Array[Int](n)
  private var numEdge: Int = 0

  def numVertices(): Int = mark.length

  def numEdges(): Int = numEdge

  def first(v: Int): Option[Int] = {
    for (i <- mark.indices)
      if (matrix(v)(i) != 0) return Some(i)
    None
  }

  def next(v: Int, w: Int): Option[Int] = {
    for (i <- w + 1 until mark.length)
      if (matrix(v)(i) != 0) return Some(i)
    None
  }

  def setEdge(s: Int, g: Int, w: Int): Unit = {
    w match {
      case 0 =>
      case _ =>
        if (matrix(s)(g) != 0) numEdge += 1
        matrix(s)(g) = w
    }
  }

  override def delEdge(s: Int, g: Int): Unit = {
    if (matrix(s)(g) != 0) numEdge -= 1
    matrix(s)(g) = 0
  }

  override def isEdge(s: Int, g: Int): Boolean = matrix(s)(g) != 0

  override def weight(s: Int, g: Int): Option[Int] = {
    matrix(s)(g) match {
      case 0 => None
      case value => Some(value)
    }
  }

  def setMark(v: Int, value: Int): Unit = mark(v) = value

  def getMark(v: Int): Int = mark(v)
}
Out[7]:
defined class MatrixGraph

Adjacency list

When graph has many edges, and the state is called dense, representation using adjavenvy matrix is space efficient. However, in the practical situation, graphs are often sparse, thsat is, there are small number of edges compared to the vertices.

Adjacency list representation store all the vertices in an array of linked lists. The elements of the linked lists are information of edges. This allows us to represent a graph using $\Theta(V + E)$ space.

In [8]:
import scala.collection.mutable

case class Edge(vertex: Int, weight: Int)

class ListGraph(n: Int) extends GraphADT {
  private val vertex: mutable.ArrayBuffer[mutable.MutableList[Edge]] =
    new mutable.ArrayBuffer[mutable.MutableList[Edge]](n)
  for(i <- 0 until n) vertex += mutable.MutableList[Edge]()
  private val mark: Array[Int] = Array[Int](n)
  private var numEdge = 0

  def numVertices(): Int = mark.length

  def numEdges(): Int = numEdge

  def first(v: Int): Option[Int] = {
    vertex(v).isEmpty match {
      case true => None
      case false => Some(vertex(v).head.vertex)
    }
  }

  def next(v: Int, w: Int): Option[Int] = {
    var flag = false
    for (edge <- vertex(v)) {
      if (flag) return Some(edge.vertex)
      if (edge.vertex == w) flag = true
    }
    None
  }

  def setEdge(s: Int, g: Int, w: Int): Unit = {
    val edge = Edge(g, w)
    delEdge(s, g)
    vertex(s) += edge
  }

  def delEdge(s: Int, g: Int): Unit = {
    val newList = vertex(s).filter(_.vertex != g)
    if (newList.length < vertex(s).length) numEdge -= 1
    vertex(s) = newList
  }

  def isEdge(s: Int, g: Int): Boolean = {
    for (edge <- vertex(s))
      if (edge.vertex == g) return true
    return false
  }

  def weight(s: Int, g: Int): Option[Int] = {
    for (edge <- vertex(s))
      if (edge.vertex == g) return Some(edge.weight)
    None
  }

  def setMark(v: Int, value: Int): Unit = mark(v) = value

  def getMark(v: Int): Int = mark(v)
}
Out[8]:
import scala.collection.mutable


defined class Edge
defined class ListGraph